#include <iostream>
#include <string>
#include <unordered_map>
#include "BTree.h"
#include "STRTree.h"
#include "Constants.h"
#include <fstream>
using namespace std;

struct RoadConSocial {

	unordered_map<int, int> s_c_r; 
	RoadGraph* road_graph;
	SocialGraph* social_graph;
	BTree* b_tree;
	STRTree* str_tree;
	unordered_set<int> qRegion; 

	RoadConSocial() {
		fstream fin(connection);
		getSocialConRoad(fin);
	}

	RoadConSocial(RoadGraph* road_graph, SocialGraph* social_graph, float delta , int topK) {
		fstream fin(connection);
		getSocialConRoad(fin);

		this->road_graph = road_graph;
		this->social_graph = social_graph;

		cout << "start create b_tree :" << endl;
		cout << "-------------------------" << endl;
		clock_t tbegin = clock(), tend;
		b_tree = new BTree(road_graph, delta);
		b_tree->createTree();
		tend = clock();
		cout << "b_tree create time :  " << to_string(tend - tbegin) << "ms" << endl;
		cout << "-------------------------" << endl << endl;

		cout << "start create str_tree :" << endl;
		cout << "-------------------------" << endl;
		clock_t tbegin1 = clock(), tend1;
		str_tree = new STRTree(social_graph , topK);
		tend1 = clock();
		cout << "str_tree create time :  " << to_string(tend1 - tbegin1) << "ms" << endl;
		cout << "-------------------------" << endl << endl;
	}

	void getSocialConRoad(fstream& fin) {
		int socialNode, roadNode;
		while (fin >> socialNode >> roadNode) {
			s_c_r.emplace(unordered_map<int, float>::value_type(socialNode, roadNode));
		}
	}

	Rectangle* getQMBR(int q_id, float start_t, float delta, float sita, float& total_time, ofstream& fout, float& time_bmax) {
		qRegion = b_tree->root->bidirectionSearch(q_id, start_t, delta, sita, fout, time_bmax, total_time);
		if (qRegion.size() == 0) return new Rectangle(0, 0);
		unordered_set<int>::iterator r_node = qRegion.begin();
		Rectangle* rect = new Rectangle(road_graph->nodes[*r_node]->x, road_graph->nodes[*r_node]->y);
		while (++r_node != qRegion.end()) {
			rect->getBoundingRect(road_graph->nodes[*r_node]->x, road_graph->nodes[*r_node]->y);
		}
		return rect;
	}

	unordered_set<int> secureRangeQuery(Rectangle* rect) {
		unordered_set<int> inner_type;
		solveQuery(str_tree->root, rect, inner_type);
		return inner_type;
	}

	void solveQuery(STRNode* root, Rectangle* rect, unordered_set<int>& inner_type) {
		if (rect->isIntersection(root->MBR)) {
			for (auto child : root->child) {
				if (rect->isIntersection(child->MBR)) {
					if (child->isLeaf == false) {
						solveQuery(child, rect, inner_type);
					}
					else {
						inner_type.emplace(child->com->label);
					}
				}
			}
		}
	}

	list<pair<int, int>> getTopKFromAll(unordered_set<int>& inner_type, Rectangle* rect, int topK) {
		list<pair<int, int>> result;
		vector<list<pair<int, int>>> que;
		int total = 0;
		vector<int> to_delete;
		int count = 0;
		for (auto label : inner_type) {
			Community* com = social_graph->community[label];
			if (rect->isContain(com->rect)) {
				count++;
				que.push_back(com->com_topk);
				total += com->com_topk.size();
				to_delete.push_back(label);
			}
		}

		if (count == 0) return result;

		for (auto del_label : to_delete) {
			inner_type.erase(del_label);
		}

		topK = total > topK ? topK : total;
		for (int i = 0; i < topK; i++) {
			int max_degree = INT_MIN;
			int pos = -1;
			for (int j = 0; j < count; j++) {
				if (!que[j].empty()) {
					if (que[j].begin()->second > max_degree) {
						max_degree = que[j].front().second;
						pos = j;
					}
				}
			}
			if (que[pos].begin()->second == 0) break;
			pair<int, int> temp = { que[pos].begin()->first , que[pos].begin()->second };
			result.emplace_back(temp);
			que[pos].pop_front();
		}
		return result;
	}

	list<pair<int, int>> getTopKFromPart(unordered_set<int>& inner_type, Rectangle* rect, int topK) {
		int total = 0;
		list<pair<int, int>> result;
		vector<list<pair<int, int>>> que;
		for (auto label : inner_type) {
			Community* com = social_graph->community[label];
			list<pair<int, int>> temp = getIntersetion(com, rect, topK);
			if (temp.empty() == true) continue;
			total += temp.size();
			que.emplace_back(temp);
		}

		topK = total > topK ? topK : total;
		int len = que.size();
		for (int i = 0; i < topK; i++) {
			int max_degree = INT_MIN;
			int pos = -1;
			for (int j = 0; j < len; j++) {
				if (!que[j].empty()) {
					if (que[j].begin()->second > max_degree) {
						max_degree = que[j].front().second;
						pos = j;
					}
				}
			}
			if (que[pos].begin()->second == 0) break;
			pair<int, int> temp = { que[pos].begin()->first , que[pos].begin()->second };
			result.emplace_back(temp);
			que[pos].pop_front();
		}
		return result;
	}

	list<pair<int, int>> getIntersetion(Community* com, Rectangle* rect, int topK) {
		list<pair<int, int>> result;
		unordered_set<int> target;
		for (auto num : com->socialPoint) {
			if (rect->isInner(social_graph->nodes[num]->x, social_graph->nodes[num]->y)) { 
				if (qRegion.find(s_c_r[num]) != qRegion.end()) { 
					target.emplace(num); 
				}
			}
		}
		if (target.empty()) return result;
		topK = target.size() > topK ? topK : target.size();
		result = com->findTopKPart(social_graph->nodes, topK, target);
		return result;
	}

	list<pair<int, int>> combineAll_PartTopK(list<pair<int, int>> all, list<pair<int, int>> part, int topK) {
		if (all.empty()) return part;
		if (part.empty()) return all;
		topK = min(all.size() , part.size());
		list<pair<int, int>> result;
		int count = 0;
		while (count < topK && !all.empty() && !part.empty()) {
			if (all.begin()->second > part.begin()->second) {
				pair<int, int> temp = { all.begin()->first , all.begin()->second };
				result.emplace_back(temp);
				all.pop_front(); 
				count++;
			}
			else if (all.begin()->second < part.begin()->second) {
				pair<int, int> temp = { part.begin()->first , part.begin()->second };
				result.emplace_back(temp);
				part.pop_front();
				count++;
			}
			else {
				pair<int, int> temp = { all.begin()->first , all.begin()->second };
				result.emplace_back(temp);
				all.pop_front();
				temp = { part.begin()->first , part.begin()->second };
				result.emplace_back(part.front());
				part.pop_front();
				count += 2;
			}
		}
		list<pair<int, int>> que = all.empty() == true ? part : all;
		while (count < topK && !que.empty()) {
			pair<int, int> temp = { que.begin()->first , que.begin()->second };
			result.emplace_back(temp);
			que.pop_front();
		}
		return result;
	}

};